package org.hw.algorithm.recursion;

/**
 * @Program: demo
 * @Author: hewei
 * @Date: 2024-03-26 16:15
 * @Description:
 * 迷宫找出口，使用递归回溯求解
 **/
public class MazeSolver {
    /*空闲节点 EMPTY，墙节点 WALL，路径节点 PATH，已访问节点 VISITED*/
    private static final int EMPTY = 0;
    private static final int WALL = 1;
    private static final int PATH = 2;
    private static final int VISITED = 3;
    // 定义四个方向的行列偏移量,依次为: [上，下，左，右]
    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private int[][] maze;
    private int rows;
    private int cols;

    public MazeSolver(int[][] maze) {
        this.maze = maze;
        this.rows = maze.length;
        this.cols = maze[0].length;
    }

    /**
     * 递归找路径：
     * ------------------------------------------------------------------------------------------------------------
     * 总体原理是递归遍历每个节点的上、下、左、右四个方向上的节点并进行标记，已经遍历过的节点标记为VISITED。
     * 如果一个节点的四个方向都不满足条件，则回溯至上一级最近的还有某个方向未遍历的节点进行递归遍历。直到递归至
     * 某个节点与目标节点相同，然后回溯，并将回溯路径上的点标识为PATH，这样就找到了路径。
     *
     * 1、每个点找路径的方向次序由directions中定义的向量为依据，优先次序为：上 -> 下 -> 左 -> 右,每个节点分别在每个方向上遍历递归一次，总共四次，只遍历状态为未访问过的节点
     * 2、递归遍历每个节点上方的点并标记为已访问，直到某个节点 N 上方不满足条件，然后递归遍历节点 N 的下方的 节点E。
     * 3、假如节点 E 的上方不满足条件，然后递归遍历节点E的下、左、右节点。
     * 4、如果节点 E 的下左右节点都不满足条件。则开始回溯至上一步的 节点N，递归遍历 节点N 的左、右节点。
     * 5、依次类推，直到某个节点与目标节点坐标相同，则一直回溯至最初的节点，并将回溯路径上的节点标识为PATH。这样就找到了路径。
     * */

    /*迷宫找路径写法一：*/
    public boolean solve(int startRow, int startCol, int endRow, int endCol) {
        if (startRow == endRow && startCol == endCol) {
            maze[startRow][startCol] = PATH;
            // 到达终点，找到路径
            return true;
        }

        // 标记当前位置为已访问
        maze[startRow][startCol] = VISITED;
        printMaze(maze);
        for (int[] direction : directions) {
            int newRow = startRow + direction[0];
            int newCol = startCol + direction[1];

            // 检查新位置是否在迷宫范围内且为空地且未访问过
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && maze[newRow][newCol] == EMPTY) {
                // 递归调用，尝试新位置
                if (solve(newRow, newCol, endRow, endCol)) {
                    // 如果在新位置找到了路径，则标记当前位置为路径的一部分
                    maze[startRow][startCol] = PATH;
                    printMaze(maze);
                    return true;
                }
            }
        }
        /*如果当前节点的上下左右递归遍历完都没有找到路径，将当前节点恢复为未访问，并返回false，然后出栈进入回溯*/
        maze[startRow][startCol] = EMPTY;
        return false;
    }

    /*迷宫找路径写法二*/
    public boolean findWay(int startRow, int startCol, int endRow, int endCol) {
        if (startRow == endRow && startCol  == endCol) {
            maze[startRow][startCol] = PATH;
            return true;
        }
        /*标识当前节点为已访问*/
        maze[startRow][startCol] = VISITED;
        printMaze(maze);
//        if ((0 <= startRow && startRow < rows) && (0 <= startCol && startCol < cols)) {
//
//        }
        /*当前节点的 [上方] 分支递归遍历，如果当前节点在路径上，则标识为PATH*/
        if (startRow -1 >= 0 && maze[startRow-1][startCol]==EMPTY && findWay(startRow - 1, startCol, endRow, endCol)) {
            maze[startRow][startCol] = PATH;
            printMaze(maze);
            return true;
            /*当前节点的 [下方] 分支递归遍历，如果当前节点在路径上，则标识为PATH*/
        } else if (startRow + 1 < rows && maze[startRow+1][startCol]==EMPTY && findWay(startRow + 1, startCol, endRow, endCol)) {
            maze[startRow][startCol] = PATH;
            printMaze(maze);
            return true;
            /*当前节点的 [左方] 分支递归遍历，如果当前节点在路径上，则标识为PATH*/
        } else if (startCol - 1 >= 0 && maze[startRow][startCol-1]==EMPTY && findWay(startRow, startCol - 1, endRow, endCol)) {
            maze[startRow][startCol] = PATH;
            printMaze(maze);
            return true;
            /*当前节点的 [右方] 分支递归遍历，如果当前节点在路径上，则标识为PATH*/
        } else if (startCol + 1 < cols && maze[startRow][startCol+1]==EMPTY && findWay(startRow, startCol + 1, endRow, endCol)) {
            maze[startRow][startCol] = PATH;
            printMaze(maze);
            return true;
        }
        /*如果当前节点的上下左右递归遍历完都没有找到路径，将当前节点恢复为未访问，并返回false，然后出栈进入回溯*/
        maze[startRow][startCol] = EMPTY;
        return false;
    }

    public static void main(String[] args) {
        int[][] maze = {
                {EMPTY, EMPTY, EMPTY, EMPTY, EMPTY},
                {WALL, EMPTY, WALL, WALL, EMPTY},
                {EMPTY, EMPTY, EMPTY, EMPTY, EMPTY},
                {WALL, EMPTY, WALL, EMPTY, WALL},
                {EMPTY, EMPTY, EMPTY, EMPTY, EMPTY}
        };

        MazeSolver solver = new MazeSolver(maze);
//        boolean pathFound = solver.solve(0, 0, 4, 4);
        boolean pathFound = solver.findWay(0, 0, 4, 4);

        if (pathFound) {
            printMaze(maze);
        } else {
            System.out.println("No path found.");
        }
    }

    /*打印迷宫当前状态*/
    private static void printMaze(int[][] maze) {
        System.out.println("-----------------------------");
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        for (int[] row : maze) {
            for (int cell : row) {
                switch (cell) {
                    case PATH:
                        System.out.print("@ ");break;
                    case WALL:
                        System.out.print("# ");break;
                    case VISITED:
                        System.out.print("* ");break;
                    default:
                        System.out.print("- ");
                }
            }
            System.out.println();
        }
    }
}